// ValidateBST.cpp : Defines the entry point for the console application.

#include "stdafx.h"
#include <iostream>
#include <stack>
#include <queue>
#include <deque>
using namespace std;

#define null 0
struct TreeNode
{
    int value;
    TreeNode *left, *right;

    TreeNode() { };

    TreeNode(int v)
    {
        value=v;
        left=right=null;
    };
};

// Validate a given BST.
//
// Algorithm: Post-order traverse the tree. Using two global variables to keep
//            the minimum value from its left child and the maximum value
//            from its right child.
// Recursion
// Analysis:
//   Time Complexity: O(n)
//   Space Complexity: O(logn) ~ O(n)

bool ValidateBST_Recursive(TreeNode *node, int &min, int &max) // by ref
{
    if(!node) return true;

    int leftMin,leftMax;
    leftMin=leftMax=node->value;
    if(!ValidateBST_Recursive(node->left,leftMin,leftMax))
        return false;

    int rightMin,rightMax;
    rightMin=rightMax=node->value;
    if(!ValidateBST_Recursive(node->right,rightMin,rightMax))
        return false;

    if((!node->left||leftMax<node->value)&&(!node->right||rightMin>node->value))
    {
        min=leftMin;
        max=rightMax;
        return true;
    }
    else
        return false;
}

bool ValidateBST_Recursive(TreeNode *root)
{
    if(!root) return false;
    int min,max;
    return ValidateBST_Recursive(root,min,max);
}


// Algorithm: In-order traverse the given binary tree. If the currently visited node's
//            value is ALWAYS GREATER than the last visited node's value, it's a BST.
// Recursion
bool ValidateBST(TreeNode *node, TreeNode *&prev) // by ref
{
    if(!node) return true;

    if(!ValidateBST(node->left,prev)) return false;

    if(prev&&prev->value>=node->value)
    {
        return false;
    }
    else
    {
        prev=node;
    }

    return ValidateBST(node->right,prev);
}

bool ValidateBST(TreeNode *root)
{
    if(!root) return false;
    TreeNode *prev=null;
    return ValidateBST(root,prev);
}


// Iteration
// Analysis:
//   Time Complexity: O(n)
//   Space Complexity: O(logn) ~ O(n)
bool ValidateBST_Iterative(TreeNode *root)
{
    if(!root) return false;

    stack<TreeNode *> s;
    s.push(root);
    int last=0; // 0: from up, 1: from left, 2: from right
    TreeNode *prev=null;

    while(!s.empty())
    {
        TreeNode *p=s.top();
        if(last==0)
        {
            if(p->left)
            {
                last=0;
                s.push(p->left);
            }
            else
            {
                last=1;
            }
        }
        else if(last==1)
        {
            // Compare current to its in-order predecessor
            if(prev && prev->value >= p->value)
            {
                return false;
            }
            else
            {
                prev=p;
            }

            if(p->right)
            {
                last=0;
                s.push(p->right);
            }
            else
            {
                last=2;
            }
        }
        else if(last==2)
        {
            s.pop();
            if(!s.empty()&&s.top()->left==p)
            {
                last=1;
            }
            else
            {
                last=2;
            }
        }
        else
            throw; // error
    }

    return true;
}

int _tmain(int argc, _TCHAR* argv[])
{
    return 0;
}